package com.example.demo;

import com.example.demo.entity.TreeNode;
import org.junit.jupiter.api.Test;

import java.util.Stack;

public class BinaryTree {

    private final TreeNode root = new TreeNode(1, "A");

    //   A
    // B   C
    //D  E   F
    public void createBinaryTree() {
        TreeNode nodeB = new TreeNode(2, "B");
        TreeNode nodeC = new TreeNode(3, "C");
        TreeNode nodeD = new TreeNode(4, "D");
        TreeNode nodeE = new TreeNode(5, "E");
        TreeNode nodeF = new TreeNode(6, "F");
        root.left = nodeB;
        root.right = nodeC;
        nodeB.left = nodeD;
        nodeB.right = nodeE;
        nodeC.right = nodeF;
    }

    @Test
    public void heightOfTreeTest() {
        createBinaryTree();
        int height = heightOfTree(root);
        System.out.println(height);
    }

    private int heightOfTree(TreeNode node) {
        if (node == null) return 0;
        int leftH = heightOfTree(node.left);
        int rightH = heightOfTree(node.right);
        return Math.max(leftH, rightH) + 1;
    }

    @Test
    public void getSize() {
        createBinaryTree();
        int size = getSize(root);
        System.out.println(size);
    }

    private int getSize(TreeNode node) {
        if (node == null) return 0;
        return 1 + getSize(node.left) + getSize(node.right);
    }

    //    A
    // B     C
    //D  E     F
    @Test
    public void preOrder() {
        createBinaryTree();
        preOrder(root);
    }

    // 先打印，再递归左右节点
    private void preOrder(TreeNode node) {
        if (node == null) return;
        System.out.println("preOrder data:" + node.getData());
        preOrder(node.left);
        preOrder(node.right);
    }

    @Test
    public void midOrder() {
        createBinaryTree();
        midOrder(root);
    }

    // 先递归左节点，再打印，再递归右节点
    private void midOrder(TreeNode node) {
        if (node == null) return;
        midOrder(node.left);
        System.out.println("midOrder data:" + node.getData());
        midOrder(node.right);
    }

    @Test
    public void postOrder() {
        createBinaryTree();
        postOrder(root);
    }

    // D E B F C A，先递归左右节点再打印
    private void postOrder(TreeNode node) {
        if (node == null) return;
        postOrder(node.left);
        postOrder(node.right);
        System.out.println("postOrder data:" + node.getData());
    }

    @Test
    public void preOrder2() {
        createBinaryTree();
        preOrder2(root);
    }

    private void preOrder2(TreeNode node) {
        if (node == null) return;
        Stack<TreeNode> stack = new Stack<>();
        stack.push(node);
        while (!stack.isEmpty()) {
            TreeNode n = stack.pop();
            System.out.println("nonRecOrder data" + n.getData());
            if (n.right != null) {
                stack.push(n.right);
            }
            if (n.left != null) {
                stack.push(n.left);
            }
        }
    }
}
